package main

import (
	"fmt"
)

/*
1.剪枝 -- 将group中大于G的数据剔除，因为要求过大，没必要考虑。
2.将profit中分为大于P和小于P的两个数组
*/
func profitableSchemes1(G int, P int, group []int, profit []int) int {
	result := 0
	for i := 1; i < len(group)-1; i++ {
		a := combine(0, len(group)-1, 1, G, P, group, profit)
		fmt.Println(a)
		if a == 0 {
			break
		}
		result += a
	}

	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/*
另d[i][j] 表示最大的多少种取法，那么
*/
func profitableSchemes(G int, P int, group []int, profit []int) int {
	var M int = 1e9 + 7
	n := len(profit)
	dp := make([][][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp2 := make([][]int, G+1, G+1)
		for j := 0; j < G+1; j++ {
			dp1 := make([]int, P+1)
			for k := 1; k < P+1; k++ {
				dp1[k] = 0
			}
			dp1[0] = 1
			dp2[j] = dp1
		}
		dp[i] = dp2
	}
	for i := 1; i <= n; i++ {
		g := group[i-1]
		p := profit[i-1]
		for j := 1; j < G+1; j++ {
			for k := 0; k < P+1; k++ {
				dp[i][j][k] = dp[i-1][j][k]
				if j >= g {
					dp[i][j][k] += dp[i-1][j-g][max(k-p, 0)]
				}
				dp[i][j][k] %= M
			}
		}
	}
	fmt.Println(dp)
	return dp[n][G][P]

}

//在sorted arr数组中下标范围[s,e)中查找距离k最近的小于k的数的下标
//没有就返回-1
func binary_search_small(s, e int, arr []int, k int) int {
	if s > e || len(arr) < 1 {
		return -1
	}
	if s == e {
		if arr[s] <= k {
			return s
		}
	}
	if s+1 == e {
		if arr[e] <= k {
			return e
		}
		if arr[s] <= k {
			return s
		}
		return -1
	}
	c := (e-s)/2 + s
	fmt.Println(c, e, s)
	if arr[c] < k {
		return binary_search_small(c, e, arr, k)
	}
	if arr[c] == k {
		return c
	}
	return binary_search_small(s, c-1, arr, k)
}

func binary_search_big(s, e int, arr []int, k int) int {
	if s > e || len(arr) < 1 {
		return -1
	}
	if s == e {
		if arr[s] >= k {
			return s
		}
	}
	if s+1 == e {
		if arr[s] >= k {
			return s
		}
		if arr[e] >= k {
			return e
		}
		return -1
	}
	c := (e-s)/2 + s
	if arr[c] > k {
		return binary_search_big(s, c, arr, k)
	}
	if arr[c] == k {
		return c
	}
	return binary_search_big(c+1, e, arr, k)
}

func combine(s, e, m int, G, P int, group, profit []int) int {
	if G <= 0 {
		return 0
	}
	if m > e-s+1 {
		return 0
	}
	if e-s+1 <= 0 || m <= 0 {
		return 0
	}
	//var result int
	if m == 1 {
		//i := s
		//j := 0
		//二分查找最靠近G的数字下标，
		center := binary_search_small(s, e, group, G)
		//没找到符合条件的就直接返回0
		if center == -1 {
			return 0
		}
		center2 := binary_search_big(s, e, profit, P)
		if center2 == -1 {
			return 0
		}
		return center2 - center + 1
		//假设在选中了几个的前提下
		//for ;i<center;i++{
		//	if profit[i]>=P{
		//		j +=1
		//	}
		//}
		//return j
	}
	result := 0
	if m > 1 {
		for j := s + 1; j <= e-m+1; j++ {
			//fmt.Println(":",j,e)
			//fmt.Println()
			r := combine(j, e, m-1, G-group[j-1], P-profit[j-1], group, profit)
			if r == 0 {
				break
			}
			result += r

			//fmt.Println(result)
		}
		//return result
	}
	return result
}

func main() {
	G := 5
	P := 3
	group := []int{2, 2, 3, 4}
	profit := []int{2, 3, 5, 6}
	//d(0,0,0)=1,d(0,1)=1,(1,3)
	//profit := []int{1, 2, 3, 4, 5, 6, 7}
	//c(profit, 2)
	//r := combine(0,3,2,G,P,group,profit)
	//fmt.Println(r)
	r := profitableSchemes(G, P, group, profit)
	fmt.Println(r)

	//arr := []int{1,3,4,5,6,7,9,11}
	//a := binary_search_big(0,len(arr)-1, arr,0)
	//fmt.Println(a)
}
